The invention relates to routing in networks, more particularly to a method and apparatus for facilitating fast routing at a network node. The routing (forwarding) stage it deals with is called xe2x80x9caddress lookup in routing (forwarding) tables.xe2x80x9d Given information designating which destination address has to be forwarded to which output port at a node, the stage organizes the information such that the on line search for this information (when a message/packet arrives at the node) is efficient in time and space consumed. The invention concerns with setting, performing and maintaining this stage. The invention is suitable (and is tuned to) the prevalent setting of Internet routing where addresses are called IP addresses. The invention is related to fast methods for solving the above problem within a standard processor architecture and with a small number of memory accesses. Due to fast routing, the invention is related to the issue of increased network bandwidth.
Computer networks are expected to exhibit very high performance in delivering data because of the explosive growth of Internet nodes (from 100,000 hosts in 1989 to over 60 millions as of 1999). The network bandwidth, which measures the number of bits that can be transmitted in a certain period of time, is thus continuously improved by adding new links and/or by improving the performance of the existing ones.
Routers are at the heart of the networks in that they forward packets from input interfaces to output interfaces on the ground of the packets"" destination Internet address, which we simply call IP address. They choose which output interface corresponds to a given packet by performing an IP address lookup at their routing table. As routers have to deal with an ever increasing number of links whose performance constantly improves, the address lookup is now becoming one of the major bottlenecks in high performance forwarding engines.
The IP address lookup problem was just considered a simple table lookup problem at the beginning of Internet. Now, it is unconceivable to store all existing IP addresses explicitly because, in this case, routing tables would contain millions of entries. In the early 1990s people realized that the amount of routing information would grow enormously, and introduced a simple use of prefixes to reduce space (see Fuller, V., Li, T., Yu, J., and Varadhan, K. xe2x80x9cClassless inter-domain routing (CIDR): an address assignment and aggregation strategyxe2x80x9d RFC 1519, 1993,). Specifically, IP protocols use hierarchical addressing, so that a network contains several subnets which in turn contain several host computers. Suppose that all subnets of the network with IP address 128.96.*.* have the same routing information apart from the subnet whose IP address is 128.96.34.*. We can succinctly describe this situation by just two entries (128.96 and 128.96.34) instead of many entries for all possible IP addresses of the network. However, the use of prefixes introduces a new dimension in the IP address lookup problem: For each packet, more than one table entry can match the packet""s IP address. In this case, the applied rule consists of choosing the longest prefix match, where each prefix is a binary string that has a variable length from 8 to 32 in IPv4 (see Postel, J. xe2x80x9cInternet protocolxe2x80x9d, RFC 791, 1981,). For example, let us consider Table 1 where xcex5 denotes the empty sequence corresponding to the default output interface, and assume that the IP address of the packet to be forwarded is 159.213.37.2, that is, 10011111 11010101 00100101 00000010 in binary. Then, the longest prefix match is obtained with the fourth entry of the table and the packet is forwarded to output interface D. Instead, a packet whose IP address is 159.213.65.15, that is, 10011111 11010101 01000001 00001111 is forwarded to output interface C.
Looking for the longest matching prefix in IP routing tables represents a challenging problem since lookups must be answered very quickly. In order to get a bandwidth of, say, 10 gigabits per second with an average packet length equal to 2,000, a router should forward 5 millions of packets per second. It means that each forwarding has to be performed in approximately 200 nanoseconds and, consequently, each lookup must be realized much faster.
Several approaches have been proposed in the last few years in order to solve the IP address lookup problem. Hardware solutions, though very efficient, are expensive and some of them may become outdated quite quickly (See U.S. patent application Ser. No. 034,444, 1995 by McAuley, A., Tsuchiya, P., and Wilson, D. xe2x80x9cFast multilevel hierarchical routing table using content-addressable memoryxe2x80x9d as well as Newman, P., Minshall, G., Lyon, T., and Huston, L. xe2x80x9cIP switching and gigabit routersxe2x80x9d in IEEE Communications Magazine (January 1997)). Modern routers will use software or hardware and software combination. Next we will review the known software solutions.
A traditional implementation of routing tables (see Stevens, W., and Wright, C. xe2x80x9cTCP/IP Illustrated, Volume 2 The Implementationxe2x80x9d Addison-Wesley Publishing Company, Reading, Mass., 1995) use a version of Patricia tries, a very well-known data structure (Morrison, D. xe2x80x9cPATRICIAxe2x80x94Practical Algorithm To Retrieve Information Coded In Alfanumericxe2x80x9d in Journal of ACM 15,4 (October 1968), 514-534). In this case, it is possible to show that, for tables with n elements, the average number of examined bits is 1.44 log n (log n is logarithm to the base 2 of the number n). Thus, for n=32000, this value is bigger than 21. When compared to millions of address lookup requests served in one second, 21 table accesses are too many. Another variation of Patricia tries has been proposed in order to examine k bit each time (in Pei, T.-B. and Zukowski, C. xe2x80x9cPutting routing tables into siliconxe2x80x9d in IEEE Network, 1992, pages 42-50). However, this variation deals with either the exact matching problem or with the longest prefix matching problem restricted to prefixes whose lengths are multiples of k.
A more recent approach (by Nilsson, S., and Karlsson, G. xe2x80x9cFast address look-up for internet routersxe2x80x9d in ALEX (February 1998), Università di Trento, pp. 9-18) was inspired by the three-level data structure of Degermark, M. at al. (xe2x80x9cSmall forwarding tables for fast routing lookupsxe2x80x9d, in ACM Computer Communication Review 27, 4 (October 1997), 3-14). which uses a scheme to compress multi-bit trie nodes using a bitmap, and is based on the compression of the routing tables by means of level compressed tries, which are a powerful and space efficient representation of binary tries. This approach seems to be very efficient from a memory size point of view but it requires many bit operations which, on the current technology, are time consuming.
Another approach is based on binary search on hash tables organized by prefix lengths (in Waldvogel, M. et al. xe2x80x9cScalable high speed IP routing lookupsxe2x80x9d, in ACM Computer Communication Review 27, 4 (October 1997), 25-36). This technique is more memory consuming than the previous one but, according to the experimental evaluation presented by the authors, it seems to be very efficient from the time point of view.
A completely different way of using binary search is described in Lampson at al. (in xe2x80x9cIP lookups using multi-way and multicolumn searchxe2x80x9d ACM INFOCOM Conference, (April 1998)). It is based on multi-way search on the number of possible prefixes rather than the number of possible prefix lengths and exploits the locality inherent in processor caches.
The most recent software solution to the IP address lookup problem is the one based on controlled prefix expansion (by Srinivasan, V., and Varghese, G. in xe2x80x9cFast address lookups using controlled prefix expansionxe2x80x9d in ACM SIGMETRICS Conference (September 1998) and available full version to appear in ACM TOCS). This approach, together with optimization techniques such as dynamic programming, can be used to improve the speed of most IP lookup algorithms. When applied to trie search, it results into a range of algorithms whose performance can be tuned and that, according to the authors, provide faster search and faster insert/delete times than earlier lookup algorithms.
Any solution for m-bit IP addresses in a routing table T can be seen as a trade-off between performing a binary search on T with O(log|T|) accesses (where |T| is the number of prefixes in T) and executing a single access on a table of 2m entries obtained by fully expanding T. The above two methods are simple and available in the art. The results described in the prior art give space-efficient data structures and aim at lowering the O(log|T|) bound on the number of accesses which may be too slow for the increasing pace of messages sent via a typical router. The invention, instead, starts out from the fully expanded table with 2m entries and aim at compressing it without an excessive increase in the (constant) number of accesses. For this reason, we call it an expansion/compression method.
We exploit the fact that the relation between the 232 IP addresses and the very few output interfaces of a router is highly redundant for m=32. By expressing this relation by means of strings (thus expanding the original routing table), these strings can be compressed (using the run-length encoding scheme) in order to provide an implicit representation of the expanded routing table which is memory efficient. More important, this representation allows us to perform an address lookup in exactly three memory accesses and three clock cycles independently of the IP address. Intuitively, the first two accesses depend on the first and second half of the IP address, respectively, and provide an indirect access to a table whose elements specify the output interfaces corresponding to groups of IP addresses (see FIG. 1).
The invention gives a general paradigm which is a method for organizing a routing table for forwarding of network messages. It essentially works by associating each possible address with an address""s first portion according to some sorting. Then the method employs compacting of this representation according to a first portion (prefix) into a first index set. Then it creates a unified compressed representation of a second portion of an address (suffix) and it uses this unified representation to designate at least another index set. Using the index sets the method creates a table indexed by the sets, where the table contains the output port/interface (next hop) entries corresponding to their respective addresses.
One of the strengths and novelties of the invention is that it completely avoids any special machinery for the longest prefix match described in the prior art. It transforms any IP prefix lookup into an indirect and standard access to a space-efficient array of memory locations. Consequently, its dominant cost is really given by the number of memory accesses with no hidden cost due to the processor architecture, such as branch prediction and other architectural features known to those skilled in the art.
The invention proposed here works for all routers belonging to the Internet and will be useful for a long period of time as the Internet grows. Moreover, its dominant cost is really given by the small number of memory accesses and it can be easily implemented in hardware where the hardware technology may vary and where tables can be written in hardware registers/tables.
We note that even though the theoretical upper bound on the worst-case memory size is O(2m/2+|T|2), in fact theory is quite far from practice and that the characteristics of the routing tables will vary much slower than the rate at which cache memory size will increase. Also, sometimes only certain addresses are allowed to be routed within a sub-network. In this case the method can be adapted to deal with partial addresses and the expansion is limited.
The invention can be used to maintain routing tables in a fashion which is adaptive to the changing traffic pattern. In this sense the invention can also be viewed as a maintenance procedure.
It is the intent to combine the address finding disclosed in the invention with any routing or sub-routing mechanism that forwards information within networks or inside network elements (like routing stages in a complex switch). The methodology of actual forwarding/routing (after the forwarding goal is determined) can vary as well and can be based on combining time division or wave division multiplexing, using dedicated hardware and optics, and so on. The one familiar with the art is aware of the ways to combine quick addressing with various forwarding and routing routines. The description as an IP addressing is merely demonstrative and is not restrictive.
Based on the method disclosed, an apparatus can be devised (in hardware, software program or combination thereof) which is part of a router which is a computer performing the task of a network node. The node contains memory, cache memory and processing elements. The apparatus comprising means which are able to perform the various parts and stages as part of a router""s function facilitating message forwarding and network routing.
It is the objective of this invention to achieve an adaptive mechanism to organize the IP lookup table (for message forwarding according to IP address).
It is further an objective of the invention to allow routing and forwarding mechanism that only looks at the IP address table a constant number of times (3 times). This results in a new mechanism for lookup, which is much faster and which implies increased speed of the routing mechanism and increased network bandwidth.
It is an objective of the invention to have a mechanism which is simple and runs on standard processors with no special computing power. To achieve the method""s basic paradigms and operational stages new mechanisms are disclosed inhere.